Section: New Results

Robust/Stochastic programming

Locating stations in a one-way electric car sharing system under demand uncertainty: We focused in [60] on a problem of locating recharging stations in one-way station based electric car sharing systems which operate under demand uncertainty. We modeled this problem as a mixed integer stochastic program and develop a Benders decomposition algorithm based on this formulation. We integrated a stabilization procedure to our algorithm and conduct a large-scale experimental study on our methods. To conduct the computational experiments, we developed a demand forecasting method allowing to generate many demand scenarios. The method was applied to real data from Manhattan taxi trips.

Integrated shift scheduling and load assignment optimization for attended home delivery: We studied an integrated shift scheduling and load assignment optimization problem for attended home delivery. The proposed approach is divided into two phases, each one corresponding to a different planning level: tactical and operational. In the tactical planning, a daily master plan is generated for each courier. This master plan defines the working shifts, the origin-destination pairs to visit, and the number of client requests to serve. In the operational planning, delivery orders are allocated to couriers in real-time. The stochastic and dynamic nature of client orders is included in the tactical and operational decision levels, respectively. For the tactical level, we developed and implemented a multi-cut L-shaped algorithm. Experimental results demonstrate that our approach provides robust tactical solutions that easily accommodate to fluctuations in client orders, preventing additional costs related to the underutilization of couriers and to the use of external couriers to satisfy all delivery requests, when compared to an approach using the mean demand value. Moreover, these results also indicate that the failure to incorporate robust tactical solutions in the operational planning results in infeasible operational plans that are inadmissible regarding the couriers' working time (e.g., minimum and maximum number of working hours) and work regulations (e.g., allocation of consecutive working hours to the couriers).

Bookings in the European gas market: Characterization of feasibility and computational complexity results: As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special long-term capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry or exit nodes of the network. These supplies and withdrawals are nominated at the day-ahead. These bookings then need to be feasible, i.e., every nomination that complies with the given bookings can be transported. While checking the feasibility of a nomination can typically be done by solving a mixed-integer nonlinear feasibility problem, the verification of feasibility of a set of bookings is much harder. We consider the question of how to verify the feasibility of given bookings for a number of special cases. For our physics model we impose a steady-state potential-based flow model and disregard controllable network elements. We derive a characterization of feasible bookings, which is then used to show that the problem is in coNP for the general case but can be solved in polynomial time for linear potential-based flow models. Moreover, we present a dynamic programming approach for deciding the feasibility of a booking in tree-shaped networks even for nonlinear flow models [56].